package com.heyqing.topic.IsValid_0020;

import java.util.LinkedList;
import java.util.Queue;
import java.util.Stack;

/**
 * ClassName:IsValid_0020
 * Package:com.heyqing.topic.IsValid_0020
 * Description:
 *
 * @Date:2024/5/18
 * @Author:Heyqing
 */
public class IsValid_0020 {
    /**
     * 栈和队列
     *
     * @param s
     * @return
     */
    public boolean isValid(String s) {
        if (s.length() == 0) {
            return true;
        }
        Stack<Character> stack = new Stack<>();
        Queue<Character> queue = new LinkedList<>();
        for (int i = 0; i < s.length(); i++) {
            if (s.charAt(i) == '{' || s.charAt(i) == '[' || s.charAt(i) == '(') {
                stack.push(s.charAt(i));
            }
            if (s.charAt(i) == '}' || s.charAt(i) == ']' || s.charAt(i) == ')') {
                if (!stack.isEmpty()) {
                    Character top = stack.peek();
                    int flag = 0;
                    switch (s.charAt(i)) {
                        case '}': {
                            if (top.equals('{')) {
                                stack.pop();
                                flag = 1;
                            }
                            break;
                        }
                        case ']': {
                            if (top.equals('[')) {
                                stack.pop();
                                flag = 1;
                            }
                            break;
                        }
                        case ')': {
                            if (top.equals('(')) {
                                stack.pop();
                                flag = 1;
                            }
                            break;
                        }
                    }
                    if (flag == 0) {
                        queue.add(s.charAt(1));
                    }
                } else {
                    return false;
                }
            }
        }
        if (!queue.isEmpty() && !stack.isEmpty()) {
            for (int i = 0; i < queue.size(); i++) {
                Character start = queue.peek();
                if (stack.isEmpty()) return false;
                Character top = stack.peek();
                switch (start) {
                    case '}': {
                        if (top.equals('{')) {
                            stack.pop();
                        }
                        break;
                    }
                    case ']': {
                        if (top.equals('[')) {
                            stack.pop();
                        }
                        break;
                    }
                    case ')': {
                        if (top.equals('(')) {
                            stack.pop();
                        }
                        break;
                    }
                }
            }
            return false;
        }
        if (!queue.isEmpty() || !stack.isEmpty()) {
            return false;
        }
        return true;
    }
}
